package leetcode;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {

	public static void main(String[] args) {
		GenerateParenthesis generate = new GenerateParenthesis();
		System.out.println(generate.generateParenthesis(3));
	}
	public List<String> generateParenthesis(int n) {
		List<String> list = new ArrayList<String>();
		if (n == 0) {
			return list;
		}
		backtrack(list, new StringBuilder(), n, n);
		return list;
	}
	
	//采用回溯的思想做
	public void backtrack(List<String> list, StringBuilder builder, int left, int right){
		//首先需要添加的是（
		//right ==0 表示的是添加完了所有的括号
		if(right == 0){
			list.add(builder.toString());
			return ;
		}
		//left 大于0对应着左括号还没有使用完，我们可以先使用左括号，
		//或者如果右括号的数目大于左括号，我们先让右括号与之配对
		if(left > 0){
			backtrack(list, builder.append("("), left - 1, right);
			builder.deleteCharAt(builder.length() - 1);
		}
		//如果右括号的数目大于左括号，我们可以使之配对
		//等于是不行的，不然会出现右括号出现在左边的情况
		if(right > left){
			backtrack(list, builder.append(")"), left, right - 1);
			builder.deleteCharAt(builder.length() - 1);
		}
	}
}
